/**
 * 给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
 *
 * 已知存在楼层 f ，满足0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
 *
 * 每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
 *
 * 请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
 *
 * 链接：https://leetcode.cn/problems/super-egg-drop
 * 题解：https://labuladong.gitee.io/algo/3/28/91/
 */
class SuperEggDrop {
    /**
     * 法一：递归版动规，但是会超时
     * dp(k,i)表示k个鸡蛋，n层楼，最坏扔鸡蛋的次数，我们要在最坏中选最小
     */
    int[][] memo;

    public int superEggDropDP1(int k, int n) {
        memo = new int[k + 1][n + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -999);
        }
        return dp1(k, n);
    }

    //k个鸡蛋,n层楼,返回最优结果
    public int dp1(int k, int n) {
        //base case
        if (k == 1) {
            return n;
        }
        if (n == 0) {
            return 0;
        }

        //备忘录
        if (memo[k][n] != -999) {
            return memo[k][n];
        }

        int res = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            res = Math.min(res, Math.max(dp(k - 1, i - 1),
                    dp(k, n - i)) + 1);
        }

        memo[k][n] = res;
        return res;
    }

    /**
     * 法二:递归版动规+二分
     * @param k
     * @param n
     * @return
     */
    public int superEggDropDp2(int k, int n) {
        memo=new int[k+1][n+1];
        for(int[] row:memo) {
            Arrays.fill(row,-999);
        }
        return dp2(k,n);
    }
    public int dp2(int k,int n) {
        if(n==0) {
            return 0;
        }
        if(k==1) {
            return n;
        }
        if(memo[k][n]!=-999) {
            return memo[k][n];
        }
        int res=Integer.MAX_VALUE;
        int left=1;
        int right=n;
        while(left<=right) {
            int mid=left+((right-left)>>>1);
            int broken=dp(k-1,mid-1);//鸡蛋碎了
            int not_broken=dp(k,n-mid);//鸡蛋没碎
            if(broken>not_broken) {
                right=mid-1;
                res=Math.min(res,broken+1);
            } else {//这里将broken<not_broken的结果和在一起，因为答案是两直线的交点，只有一个答案，所以左侧边界搜索和右侧边界搜索都是一样的
                left=mid+1;
                res=Math.min(res,not_broken+1);
            }
        }
        memo[k][n]=res;
        return res;
    }
    /**
     * 法三：修改dp[k][m]的定义，dp[k][m]=n表示有K个鸡蛋，可以尝试扔m次，最坏情况下最多能确切测试出n层的楼，也就是当dp[k][m]=n时，求m的最小值
     *
     */

    public int superEggDropDp3(int K, int n) {
        int[][] dp=new int[K+1][n+1];
        int m=0;
        while(dp[K][m]<n) {
            m++;
            for(int k=1;k<=K;k++) {
                dp[k][m]=dp[k-1][m-1]+dp[k][m-1]+1;
            }
        }
        return m;
    }
   
}